package dynamic;

import dynamic.domain.PointFlag;

import java.util.*;

/**
 * 矩阵最小路径和
 *
 * @author 罗俊华
 * @date 2021/7/20 - 2:30 下午
 */
public class MatrixMinimumPathSum {

    PointFlag[][] array;

    public MatrixMinimumPathSum(int[][] arr) {
        PointFlag[][] A = new PointFlag[arr.length][];
        for (int i = 0; i < arr.length; i++) {

            PointFlag[] a = new PointFlag[arr[i].length];

            for (int j = 0; j < arr[i].length; j++) {
                a[j] = new PointFlag(i, j, arr[i][j]);
            }
            A[i] = a;
        }
        this.array = A;
    }



    public int searchEntry() {

        Map<PointFlag, Integer> cache = new HashMap<>();
        return search(array[0][0], cache);
    }

    private int search(PointFlag parentPoint, Map<PointFlag, Integer> cache) {

        Integer cachedCost = cache.get(parentPoint);

        if (cachedCost != null) {
            return cachedCost;
        }

        int pathLength = Integer.MAX_VALUE;

        List<PointFlag> availableNextStep = getAvailableNextStep(parentPoint);

        for (PointFlag pointFlag : availableNextStep) {


            if (finished(pointFlag)) {

                return parentPoint.getWeight() + pointFlag.getWeight();

            } else {

                int searchCost = this.search(pointFlag,cache);

                pathLength = Math.min(pathLength, searchCost);

            }

        }

        cache.put(parentPoint, pathLength + parentPoint.getWeight());

        return pathLength + parentPoint.getWeight();
    }

    private boolean finished(PointFlag pointFlag) {

        return pointFlag.getX() == array.length - 1 && pointFlag.getY() == array[0].length - 1;
    }

    List<PointFlag> getAvailableNextStep(PointFlag pointFlag) {
        return this.getAvailableNextStep(pointFlag.getX(), pointFlag.getY());
    }

    /**
     * 获得当前点可以走的下一步的点是那几个
     *
     * @param x
     * @param y
     * @return
     */
    List<PointFlag> getAvailableNextStep(int x, int y) {

        List<PointFlag> result = new ArrayList<PointFlag>(4);

//     向右走
        if (x + 1 < array.length && !array[x + 1][y].isVisited()) {
            result.add(array[x + 1][y]);
        }

//      向下走
        if (y + 1 < array[0].length && !array[x][y + 1].isVisited()) {
            result.add(array[x][y + 1]);

        }


       /* if (y - 1 >= 0 && !array[x][y - 1].isVisited()) {
            result.add(array[x][y - 1]);

        }

        if (x - 1 >= 0 && !array[x - 1][y].isVisited()) {
            result.add(array[x - 1][y]);
        }*/

        return result;

    }


}
